1. Field of the Invention
The invention relates to algorithmic procedures for compressing, recompressing and decompressing digital media. More specifically, the invention relates to automated data sequencing, modeling encoding and decoding for converting media types such as text, audio, image, and video originally stored in an uncompressed or compressed formats such as bitmap, MP3, JPEG, or MPEG into a new compressed format. In a more particular embodiment, the invention includes both: the sequential and progressive compressing/recompressing and decompressing modes.
2. Description of the Relevant Art
Media formats specify how a type of file should be packaged. Specifically, formats specify how information describing a file should be represented as digital data. Often, formats describing files containing large amounts of data include a method for which to compress the file and to decompress it. This minimizes the amount of data needed to contain the file by removing extraneous information and statistical redundancies. In turn, this allows for more efficient transfer of the file from hard drives to memory and back, or over communications networks.
In particular, digital audio and visual media necessarily contain large amounts of data due to the fact that they should provide the perception of smooth, continuous input to human sensory systems despite the inherent granularity of a digital representation. Fortunately, human perception is not adept at distinguishing subtle variations in sensory signals. This allows digital representations of sensory data to be compressed lossily by discarding or smoothing over data which is not easy for a human to perceive. Smoothing is especially effective if data is highly correlated as small structural changes will not be apparent.
Furthermore, highly correlated data implies that if a portion of that data be removed, it is possible to estimate and reinsert that portion of the data. The task of lossy compression is to locate and discard data which can be adequately estimated using some method.
Some of the most successful lossy compression algorithms utilize one or another types of reversible (or nearly-reversible) decorrelating transforms on successive partitions of data. The purpose of a transform is to re-represent each partition of data in such a way that correlated information is concentrated into certain regions of the transform domain while less correlated data is spread into other regions of the transform domain. Thus, an effective transform “decorrelates” data into a sparser representation. If the transform is properly chosen to decorrelate a partition of interest, then the majority of the relevant partition information is concentrated into only a few regions of the transform domain. By intelligently discarding or smoothing regions in the transform domain (usually in quantization steps involving scaling and rounding), the complexity of the underlying data can be reduced while minimally impacting the perceived quality of that underlying data. Reduced complexity simplifies statistical and predictive models which in turn allow for more effective data compression during an entropy encoding stage. Such decorrelating transforms include, but are not limited to, the Karhunen-Loève transform (KLT), the discrete cosine transform (DCT) family, the wavelet transform families and integer transform families which utilize nonlinear lifting-schemes.
Older formats like the original JPEG standard for image compression do not generally preserve apparent data fidelity as well as more modern formats at similar compression rates. But some older compression algorithms have endured and in many cases have become de facto digital standards. This is apparent in dominance of JPEG image media over more modern formats. The original JPEG format, released in 1992, was the culmination of two decades of research into linear transform coding and quantization for image compression. Before JPEG, no single standard could obtain low enough bitrates at acceptable quality levels for standard resolution, color images which would allow for efficient storage and distribution of digital, visual media. Since then, newer proprietary formats along with JPEG-LS, JPEG-2000, and the JPEG-XR format have sought to increase the coding efficiency of the original JPEG algorithm while simultaneously enhancing its feature set. However, the new formats have failed to gain widespread acceptance by most users due to a number of factors. These factors may include: a) the new formats may be computationally demanding and require faster computers to support a pleasant user experience; b) the new formats may not add much compression performance over the original JPEG standard; c) the new formats may not add substantial visual improvement at comparable bit rates to the original JPEG standard; d) JPEG format pictures may already be in wide distribution; e) use of the JPEG standard does not incur licensing fees; f) transcoding of already-compressed JPEG images into more advanced lossy format may result in poor image quality; and g) transcoding of already-compressed JPEG images into more advanced lossless format may not result in a significantly smaller file size. Even so, the JPEG standard is 20 years old and offers inferior bit rates at comparable quality to more modern formats.